package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/13 20:32
 * @description：https://leetcode-cn.com/problems/the-skyline-problem/
 */
public class 天际线问题 {
    @Test
    public void test() {
        Solution solution = new Solution();
        int[][] buildings = {{2, 9, 10}, {3, 7, 15}, {5, 12, 12}, {15, 20, 10}, {19, 24, 8}};
        solution.getSkyline(buildings);
    }

    class Solution {
        public List<List<Integer>> getSkyline(int[][] buildings) {
            ArrayList<ArrayList<int[]>> nodes = new ArrayList<>();
            ArrayList<int[]> node = new ArrayList<>();
            for (int[] building : buildings) {
                int l = building[0];
                int r = building[1];
                int h = building[2];
                int preX = node.size() > 0 ? node.get(node.size() - 1)[0] : l;
                if (l > preX) {
                    nodes.add(node);
                    node = new ArrayList<>();
                }
                node.add(new int[]{l, h});
                node.add(new int[]{r, h});
            }
            if (node.size() > 0)
                nodes.add(node);
            /*for (ArrayList<int[]> n : nodes) {
                for (int[] ints : n) {
                    System.out.println(Arrays.toString(ints));
                }
                System.out.println();
            }*/
            List<List<Integer>> ans = new ArrayList<>();
            for (int i = 0; i < nodes.size(); i++) {
                ArrayList<int[]> n = nodes.get(i);
                for (int j = 0; j < n.size(); j++) {
                    ArrayList<Integer> sub = new ArrayList<>();
                    if (j == 0) {
                        sub.add(n.get(j)[0]);
                        sub.add(n.get(j)[1]);
                    } else if (j == n.size() - 1){
                        sub.add(n.get(j)[0]);
                        sub.add(0);
                    } else if (j % 2 == 1){
                        continue;
                    } else {
                        if (n.get(j - 1)[1] < n.get(j)[1]) {
                            sub.add(n.get(j)[0]);
                            sub.add(n.get(j)[1]);
                        } else if (n.get(j - 1)[1] == n.get(j)[1]) {
                            continue;
                        } else {
                                sub.add(n.get(j - 1)[0]);
                                sub.add(n.get(j)[1]);
                            }
                        }
                    if (ans.size() > 1) {
                        List<Integer> list = ans.get(ans.size() - 1);
                        if (list.get(0) == sub.get(0) && sub.get(1) > list.get(1)) {
                            ans.remove(ans.size() - 1);
                        } else if (sub.get(1) == list.get(1) && sub.get(0) > list.get(0)) {
                            continue;
                        }
                    }
                    ans.add(sub);
                }
            }
            return ans;
        }
    }

    /*
    class Solution {
    public List<List<Integer>> getSkyline(int[][] buildings) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> b[1] - a[1]);
        List<Integer> boundaries = new ArrayList<Integer>();
        for (int[] building : buildings) {
            boundaries.add(building[0]);
            boundaries.add(building[1]);
        }
        Collections.sort(boundaries);

        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        int n = buildings.length, idx = 0;
        for (int boundary : boundaries) {
            while (idx < n && buildings[idx][0] <= boundary) {
                pq.offer(new int[]{buildings[idx][1], buildings[idx][2]});
                idx++;
            }
            while (!pq.isEmpty() && pq.peek()[0] <= boundary) {
                pq.poll();
            }

            int maxn = pq.isEmpty() ? 0 : pq.peek()[1];
            if (ret.size() == 0 || maxn != ret.get(ret.size() - 1).get(1)) {
                ret.add(Arrays.asList(boundary, maxn));
            }
        }
        return ret;
    }
}

     */

}
